package com.ayuer.chapter10;

import java.util.*;

public class HuffmanTree {

    String str;

    Map<Character, Node> map = new HashMap<>();

    Node root;

    StringBuilder sb = new StringBuilder();

    public static class Node {
        Character ch;
        Node left;
        Node right;
        int freq;
        String code;

        public Node(Character ch) {
            this.ch = ch;
        }

        public Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "ch=" + ch +
                    ", left=" + left +
                    ", right=" + right +
                    ", freq=" + freq +
                    ", code='" + code + '\'' +
                    '}';
        }
    }

    public HuffmanTree(String str) {
        //1.统计词频
        this.str = str;
        char[] chars = str.toCharArray();
        for (char c : chars) {
            if (!map.containsKey(c)) {
                Node node = new Node(c);
                map.put(c, node);
            }
            Node node = map.get(c);
            node.freq = node.freq + 1;
        }
        Collection<Node> values = map.values();
        for (Node value : values) {
            System.out.println(value);
        }
        //2.构造哈夫曼树
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.freq));
        queue.addAll(values);
        while (queue.size() >= 2) {
            Node first = queue.poll();
            Node second = queue.poll();
            int freq = first.freq + second.freq;
            queue.add(new Node(freq, first, first));
        }
        root = queue.poll();
        //3.计算字符编码
        dfs(root, sb);

    }

    private void dfs(Node root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        //叶子节点
        if (root.left == null) {
            root.code = sb.toString();
            System.out.println(sb);
        } else {
            dfs(root.left, sb.append("0"));
            dfs(root.right, sb.append("1"));
        }
        //删除
        if (!sb.isEmpty()) {
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    //4.解码
    public String decode(String str) {
        char[] chars = str.toCharArray();
        int i = 0;
        Node curr = root;
        StringBuilder sb = new StringBuilder();
        while (i < chars.length) {
            //当前的char
            char ch = chars[i];
            //判断是叶子节点
            if (curr.left == null) {
                //重置
                curr = root;
                sb.delete(0, sb.length());
            } else {
                if (ch == '0') {
                    curr = curr.left;
                } else {
                    curr = curr.right;
                }
                sb.append(ch);
            }
            i++;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree("abbccccccc");
        huffmanTree.decode("");
    }
}

